package testrank.affinity;


public class EditDistanceCalculator {
	private static int ComputeDistance (String s, String t)
	{
	    int n=s.length();
	    int m=t.length();
	    int[][] distance=new int[n + 1][m + 1]; // matrix
	    int cost=0;
	    if(n == 0) return m;
	    if(m == 0) return n;
	    //init1
	    for(int i=0; i <= n; distance[i][0]=i++);
	    for(int j=0; j <= m; distance[0][j]=j++);
	    //find min distance
	    for(int i=1; i <= n; i++)
	    {
	        for(int j=1; j <= m;j++)
	        {
	            cost = t.charAt(j - 1) == s.charAt(i - 1) ? 
	            		0 : 1;
	            distance[i][j]= min3(
	            		distance[i - 1][j] + 1,
	            		distance[i][j - 1] + 1,
	            		distance[i - 1][j - 1] + cost);
	        }
	    }
	    return distance[n][m];
	}

	private static float ComputeDistanceCaseSensitive(String s, String t)
	{
	    int n=s.length();
	    int m=t.length();
	    float[][] distance=new float[n + 1][m + 1]; // matrix
	    float cost=0;
	    if(n == 0) return m;
	    if(m == 0) return n;
	    //init1
	    for(int i=0; i <= n; distance[i][0]=i++);
	    for(int j=0; j <= m; distance[0][j]=j++);
	    //find min distance
	    for(int i=1; i <= n; i++)
	    {
	        for(int j=1; j <= m;j++)
	        {
	            cost = 
	            	t.charAt(j - 1) == s.charAt(i - 1) ? 0F :
	            	Character.toLowerCase(t.charAt(j - 1)) == Character.toLowerCase(s.charAt(i - 1)) ? 0.5F : 
           			1F;
	            distance[i][j]= min3F(
	            		distance[i - 1][j] + 1,
	            		distance[i][j - 1] + 1,
	            		distance[i - 1][j - 1] + cost);
	        }
	    }
	    return distance[n][m];
	}

	private static int min3(int i, int j, int k) {
		return Math.min(i, Math.min(j, k));
	}
	
	private static float min3F(float i, float j, float k) {
		return Math.min(i, Math.min(j, k));
	}

	public static float getSimilarity(String string1, String string2, boolean caseSensitive) 
	{ 
	    float dis = caseSensitive ?
	    	ComputeDistanceCaseSensitive(string1, string2) :	
	    	ComputeDistance(string1, string2);
	    float maxLen=string1.length();
	    if (maxLen < string2.length())
	    maxLen = string2.length();
	    if (maxLen == 0.0F)
	    return 1.0F;
	    else
	    return 1.0F - dis/maxLen; 
	}
	
	
	private static void test(String a, String b, boolean caseSensitive) {
	    float dis=caseSensitive ? ComputeDistanceCaseSensitive(a, b) : ComputeDistance(a, b);
	    float sim = getSimilarity(a, b, caseSensitive);
		System.out.println(a + ", " + b + " \t" + dis + " \t" + sim);		
	}
	public static void main(String[] args) {
		test("a", "b", false);
		test("a", "ab", false);
		test("kitten", "sitting", false);
		test("Saturday", "Sunday", false);
		
		test("a", "a", true);
		test("A", "A", true);
		test("A", "a", true);
		test("a", "bA", true);
		
		
	}
}
